/**
 *
 *二叉树和二叉搜索树
 *二叉树中的节点最多只能有两个子节点：
 *一个是左侧子节点，另一个是右侧子节点。
 *这些定 义有助于我们写出更高效的向/从树中插人、查找和删除节点的算法。
 *二叉树在计算机科学中的 应用非常广泛。
 *二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值， 在右侧节点存储（比父节点）大（或者等于）的值。 
 */
class Node {
	constructor(key){
		this.key = key;
		this.left = null;
		this.right = null;
	}
}

class BinarySearchTree {
	constructor(){
		this.root = null;
	}

	insert(key){
		const newNode = new Node(key);
		const insertNode = (node, newNode) => {
			if (newNode.key < node.key) {
				if (node.left === null) {
					node.left = newNode;
				} else {
					insertNode(node.left, newNode);
				}
			} else {
				if (node.right === null) {
					node.right = newNode;
				} else {
					insertNode(node.right, newNode);
				}
			}
		}
	
		if (!this.root) {
			this.root = newNode;
		} else {
			insertNode(this.root, newNode);
		}
	}

	//中序遍历
	inOrderTraverse(callback) {
	  const inOrderTraverseNode = (node, callback) => {
	    if (node !== null) {
	        inOrderTraverseNode(node.left, callback)
	        callback(node.key)
	        inOrderTraverseNode(node.right, callback)
	    }
	  }
	  inOrderTraverseNode(this.root, callback)
	}

	//先序遍历
	preOrderTraverse(callback) {
	  const preOrderTraverseNode = (node, callback) => {
	    if (node !== null) {
	      callback(node.key)
	      preOrderTraverseNode(node.left, callback)
	      preOrderTraverseNode(node.right, callback)
	    }
	  }
	  preOrderTraverseNode(this.root, callback)
	}

	//后序遍历
	postOrderTraverse(callback) {
	  const postOrderTraverseNode = (node, callback) => {
	    if (node !== null) {
	      postOrderTraverseNode(node.left, callback)
	      postOrderTraverseNode(node.right, callback)
	      callback(node.key)
	    }
	  }
	  postOrderTraverseNode(this.root, callback)
	}

	min(node) {
	  const minNode = node => {
	    return node ? (node.left ? minNode(node.left) : node) : null
	  }
	  return minNode(node || this.root)
	}

	max(node) {
	  const maxNode = node => {
	    return node ? (node.right ? maxNode(node.right) : node) : null
	  }
	  return maxNode(node || this.root)
	}
}

const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)

console.log(tree);

tree.inOrderTraverse(value => {
	console.log(value)
})

console.log(tree.max());
console.log(tree.min());
